#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
private:
    struct unit {
        int val;
        int count;
        unit(int val_, int count_) :val(val_), count(count_) {

        }
    };
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<unit>vec;
        unordered_map<int, int> map_;
        for (int i = 0; i < barcodes.size();++i) {
            ++map_[barcodes[i]];
        }
        for (auto it = map_.begin(); it != map_.end(); ++it) {
            vec.emplace_back(it->first, it->second);
        }
        sort(vec.begin(), vec.end(), [](const unit& left, const unit& right) {
            return left.count > right.count;
            });
        int j = 0;
        for (int i = 0; i < vec.size(); i++) {
            while (vec[i].count > 0) {
                barcodes[j] = vec[i].val;
                j += 2;
                if (j >= barcodes.size())
                    j = 1;
                --vec[i].count;
            }
        }
        return barcodes;
    }
};